#ifndef DGRAPHUTIL_H_INCLUDED
#define DGRAPHUTIL_H_INCLUDED

#include "DGraph.h"
#include "DTree.h"
#include "headers.h"

#include <queue>
#include <memory.h>
#include <hash_map>
class DGraphUtil {
public:
	// depth first search given a start node
	static void dfs(DGraph& g, int vid, vector<int>& preorder,
			vector<int>& postorder, vector<bool>& visited);
	// topological sorting by depth-first search
	// return reverse order of topological_sorting list
	static void topological_sort(DGraph& g, vector<int>& rts);
	// compute transitive closure
	// from Klaus Simon's paper "An improved algorithm for transitive closure on acyclic digraphs"


	//
	static void opt_topological_sort(DGraph& g, vector<int> &reverse_topo_sort,
			int opt);
	static void computePred(DGraph& g, vector<int>& reverse_topo_sort,
			int* numPreds);
private:
	static void transitive_closure(DGraph& g, DGraph& tc);
public:
	static void transitive_closure_matrix(DGraph& g,
			map<pair<int, int> , bool> &tcm);
	// generate a (right-most) spanning tree by dfs
	static void rightmost_spanning_tree(DGraph& g, DTree& tree);
private:
	//    static void rightmost_spanning_tree2(int v, vector<bool>& visited, DGraph& g, DTree& tree, NTEList& NTE);
	static int rightmost_spanning_tree2(int v, vector<bool>& visited,DGraph& graph, DTree& tree, int& post_order,
			int& level, hash_map<int, int>& pre_order_save, int& pre);
	// implement tarjan's algorithm to find Strongly Connected Component from a given start node
	static void tarjan(DGraph& g, int vid, int& index, /*hash_map*/map<int,
			pair<int, int> >& order, vector<int>& sn,
			multimap<int, int>& sccmap, int& scc);
public:
	// merge Strongly Connected Component
	// return vertex map between old vertex and corresponding new merged vertex
	static void merge_SCC(DGraph& g, int* on, vector<int>& ts);
	/*
	 static void findTreeCover(Graph g, Graph& tree);
	 static void findTreeCover(Graph g, Graph& tree, vector<set<int> >& pred);
	 static void findTreeCover(Graph g, Graph& tree, vector<set<int> >& pred, vector<int> ts);
	 static void compute_pred(Graph g, vector<set<int> >& predMap);
	 static void findTreeCoverL(Graph g, Graph& tree);
	 static void traverse(Graph& tree, int vid, int& pre_post, vector<bool>& visited);
	 static void pre_post_labeling(Graph& tree);
	 static void pathDecomposition(Graph& g, vector<vector<int> >& pathMap);
	 static void pathDecomposition(Graph& g, vector<vector<int> >& pathMap, vector<int> ts);
	 static void treePathDecomposition(Graph tree, Graph& g, vector<vector<int> >& pathMap);

	 static void genRandomGraph(int n, double c, char* filename);
	 */
};

#endif // DGRAPHUTIL_H_INCLUDED
